package leetcode.graph;

import java.util.HashSet;
import java.util.Set;

/**
 * @author wangmaolin1
 * @date 2023/11/13 22:43
 */
public class _694 {
    /**
     * 不同岛屿数量
     * <p>
     * 每个岛屿序列化为字符串，hashSet去重
     */
    int numDistinctIslands(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Set<String> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, i, j, sb, 1);
                    set.add(sb.toString());
                }
            }
        }
        return set.size();
    }

    private void dfs(int[][] grid, int i, int j, StringBuilder sb, int x) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            return;
        }
        if (grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        sb.append(x).append(",");
        dfs(grid, i + 1, j, sb, 1);
        dfs(grid, i - 1, j, sb, 2);
        dfs(grid, i, j + 1, sb, 3);
        dfs(grid, i, j - 1, sb, 4);
        sb.append((-x)).append(",");
    }
}
